1. Field of the Invention
The present invention relates to a method and an apparatus for determining occurrence of a collision of virtual objects in a virtual space generated by a virtual reality generating apparatus. More specifically, the present invention relates to a method and an apparatus for determining whether a collision between virtual objects or a collision of a virtual object and a subject in the virtual space is caused or not by a movement of the virtual objects or by a movement of a view point of the subject in the virtual space.
2. Description of the Background Art
Recently, a virtual reality system (hereinafter referred to as "VRS") have become widely applicable to computer aided education systems, simulators, amusement equipments and so on. In the VRS, a real time compute graphics image generated by a graphic processor is displayed on a Head Mounted Display (hereinafter simply referred to as HMD) with three dimensional sensors. Postures, position, head movement and so on of a subject are sensed by the sensors and based on the sense information, the displayed image is changed on real time basis. In such a VRS, the subject operates various input devices and the subject can move in a three dimensional space created by a computer (virtual space, hereinafter referred to as VR) as if the subject exists in the space.
Objects set in advance may be arranged in the VR (the object will be hereinafter referred to as "virtual object"). When the subject moves in the virtual space, the position of the point of view of the subject changes and, accordingly, the virtual objects looks differently. Thus the subject experiences the VR.
Various virtual objects may be arranged in the space in which the subject may move. The space in which actual movement of the subject is allowed should be regulated by the virtual objects. Therefore, it is essential in the VRS to determine whether the subject collides with a virtual object or not, based on the relation between the present position of the subject and the virtual object. Further, in simulating movement of a certain object (one of the virtual objects) in the virtual space, it is necessary to determine whether or not the certain object collides with another virtual object.
In the VRS, a virtual object is constituted by a number of polygons as shown for example by a chair in FIG. 8A. In a conventional collision determining apparatus, occurrence of a collision between each and every one of the number of polygons constituting the virtual object and the object of interest or the subject is determined. The chair shown in FIG. 8A includes 1277 facets. Therefore, in the prior art, a total of 1277 calculations for determining collision, one for one facet, are necessary for determining collision against only one chair.
Remarkable development in recent three dimensional real time CG (computer graphics) has allowed drawing of a huge number of polygons within a prescribed time period in the VRS. At the time of filing of this application, it is possible to draw several hundreds thousands or several millions of polygons within one second. The polygon drawing performance is closely related to a CG image expression. The larger the number of polygons which can be drawn in a prescribed time period, more real and more natural image display is possible. Current trend is to draw more real models. Therefore, the number of polygons constituting a virtual object tends to be larger.
Further, in this type of system, interactivity is of primary importance. The subject acts on a virtual object displayed in the virtual space, utilizing information input through various input devices and outputs obtained from the sensors. Reaction of the virtual object to the action of the subject is simulated by the VRS, and fed back to the subject in the form of a change in the image. This change or variation of the image recognized by the subject causes the sense as if he or she is actually in the virtual space. For this reason, high response is indispensable in image display of the VRS.
In the real space, when the subject moves in a room, at the point he or she collides against a wall, the subject cannot move further. In order to have the subject moving in the VR experience the same, it is necessary to determine whether the subject collides against other virtual objects, as described above. For this purpose, position of the subject in a virtual room set previously by a three dimensional model is set. How the room looks from the set position is found by geometric calculation. When the subject requests a movement to a certain direction, then an image which would be viewed by the subject at a position after movement is geometrically calculated at an instant, and the image is presented to the subject. The VR must reflect such variation or change on real time basis, and therefore such calculation at an instant (of at most 1/30 sec.) must be repeated.
When a virtual object such as a desk is placed in the room or a wall of the room overlaps the position of the subject, a process prohibiting further movement of the subject must be completed in the aforementioned instant and fed back to the subject. The manner of feed back may be suppression of image variation, or it may be in the form of reaction force if an apparatus causing reaction force felt by the subject is available. Anyhow, if detection of collision takes much time, feedback to the subject delays. The subject's sense as id the subject is in the space is significantly ruined, and the virtual reality is lost.
As already described, in order to enhance the sense of virtual reality, it is necessary to increase the number of polygons constituting a virtual object. In fact, the number of polygons used in the VRS is ever increasing. This increases the amount of geometric calculation for drawing, as well as the amount of calculation required for determining collision. The larger the number of virtual objects, the larger the amount of calculation. Therefore, in the conventional apparatus which performs collision determination process for every polygon constituting the virtual object (model), the amount of calculation is formidable, resulting in intolerable time of processing.
In order to reduce the amount of calculation in the process of determining collision, a method has been proposed in which one virtual rectangular parallelepiped covering the virtual object of interest is set, and the virtual object of interest is approximated by the rectangular parallelepiped. By this method, occurrence of collision of a subject (model) against the rectangular parallelepiped is determined. Consider the chair model shown in FIG. 8B. One virtual box surrounding the entire model is set, and collision of a subject model against the box is determined. By such a method, it becomes possible to calculate whether the subject collides against the chair or not, simply by performing calculation for determining the subject model and six facets constituting the virtual box, regardless of the number of polygons drawn.
However, in this method, size of the virtual rectangular parallelepiped for determining collision is defined by the maximum and the minimum coordinate values of respective coordinate axes of the three dimensional coordinate in which the model of the virtual object exists. Therefore, correct determination of collision is not possible when the shape of the model is spatially imbalanced (as in the case of a box-shaped, object having a large cavity). In this case also, the sense of the subject viewing the image would be different from the sense developed by the subject from the fedback result of collision determination, and therefore virtual reality is ruined.
Another proposal for increasing the speed of processing of collision determination and to improve preciseness or correctness of collision determination processing has been made in Japanese Patent Laying-Open No. 7-230559. In the system disclosed in this laid-open application, a virtual object is approximated by a set of three dimensional spheres and whether there is a collision between each of the spheres and a sphere approximating a model of another virtual object (for example, subject) is determined. Since an object is approximated by the simple shape (sphere), the amount of required memory is small and calculation at high speed is possible.
However, since the virtual object is approximated by the set of spheres, there is inevitably a gap between spheres. Such gap may result in erroneous determination of collision. Further, in order to find the view point of the subject and the position of drawing the virtual object after collision between the subject model and the virtual object, it is necessary to calculate reflection vector with respect to the spherical surface in accordance with complex expressions. Therefore even by this system, complicated calculation is unavoidable, and hence the time necessary for calculation is not much reduced.